package com.dbh.alg.algorithm.hot100.二叉树;

import com.dbh.alg.datastructure.queue.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *
 * 有效 二叉搜索树定义如下：
 *
 * 节点的左子树只包含 严格小于 当前节点的数。
 * 节点的右子树只包含 严格大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [2,1,3]
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 *
 *
 * 提示：
 *
 * 树中节点数目范围在[1, 104] 内
 * -231 <= Node.val <= 231 - 1
 */
public class Leetcode98_验证二叉搜索树 {

    public boolean isValidBST(TreeNode root) {
        TreeNode curr = root;
        Deque<TreeNode> stack = new LinkedList<>();
        Integer inOrder = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode pop = stack.pop();
                if (inOrder != null && pop.val <= inOrder) {
                    return false;
                }
                inOrder = pop.val;
                curr = pop.right;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Leetcode98_验证二叉搜索树 leetcode98_验证二叉搜索树 = new Leetcode98_验证二叉搜索树();
        leetcode98_验证二叉搜索树.isValidBST(new TreeNode(-2147483648));
    }
}
